package Sort.面试;

public class Sort {
    public static void main(String[] args) {

        int arr[] = {1,2,9,5,7,1,5,7,4,6,3,4,5};
//        bubbleSort(arr);
//        checkSort(arr);
        insertSort(arr);
        for(int i = 0 ; i < arr.length; i++){
            System.out.println(arr[i]);
        }
    }


    public static void bubbleSort(int array[]){
        for(int i  = 0; i < array.length ; i ++){
            for(int j  = 0; j < array.length - 1; j ++){
                if(array[j] > array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }


    public static void checkSort(int array[]){
        for(int i = 0; i < array.length -1; i++){
            int k = i;
            for(int j = k + 1; j < array.length; j++){
                if(array[k] > array[j]){
                    k = j;
                }
            }

            if(k != i){
                int temp = array[k];
                array[k] = array[i];
                array[i] = temp;
            }
        }
    }


    public static void insertSort(int arr[]){
        int temp;
        for(int i = 0 ; i < arr.length; i ++){
            temp = arr[i];
            while(i > 0 && arr[i-1] > temp){
                arr[i] = arr[i-1];
                i--;
            }
            arr[i] = temp;
        }
    }
}
